8/24/2023 Bruce Adams
The challenges of graph computations stem from both the complexity of the algorithms used and the large computing and storage requirements of many graph problems. To address these challenges, a team headed by Professor Josep Torrellas, has been awarded a $5M NSF grant for a period of 5 years.
Written by Bruce Adams
Graph applications are some of today’s most important and challenging workloads. They enable a myriad of scientific computing and data analytics applications, including:
- Biology problems such as how species evolve or proteins interact,
- Social network analysis problems such as how friends network or misinformation propagates on the internet.
- Verification of software systems to prove that software is correct.
They also act as computational bottlenecks in many data-intensive applications because of their poor data locality and high communication-to-computation ratio.
The challenges of graph computations stem from both the complexity of the algorithms used and the large computing and storage requirements of many graph problems. To address these challenges, a team headed by Principal Investigator Josep Torrellas, Saburo Muroga Professor of Computer Science and Director, SRC JUMP 2.0 ACE Center for Evolvable Computing, has been awarded a $5M NSF grant for a period of 5 years.
Their “General-Purpose Scalable Technologies for Fundamental Graph Problems” proposal outlines an ambitious, cross-layer effort to accelerate the execution of large graph problems on large, distributed machines, such as those found in data centers. As Torrellas explained,
“Graph problems are very hard to manage with existing systems. Mostly because they are very irregular. They don't use computer processors or memory systems very efficiently. They have large working sets and access a lot of scattered data. What we want to do is to design better algorithms, hardware platforms, and support software so that they are executed much more efficiently and on large-scale machines. That's the challenge: efficiency and large scale.”
The investigators are ten faculty at the University of Illinois Urbana-Champaign, Massachusetts Institute of Technology (MIT), and Indiana University, with expertise in several distinct areas. The work will be done in close collaboration with research groups at IBM and Meta. Torrellas described the process of team building:
“We had a lot of discussions. We started with a small group of faculty, and then we tried to cover all the areas from applications to software and hardware. We looked within the Grainger College of Engineering, and we were able to find most of the needed expertise.
The project covers four research areas: Theory & Algorithms led by Julian Shun, Associate Professor of Electrical Engineering and Computer Sciencen at MIT; Programming Languages & Compilers headed by Charith Mendis, Professor at Illinois; High-Performance Computing led by Ariful Azad, Assistant Professor of Intelligent Systems Engineering at Indiana University; and Computer Architecture and Hardware led by Josep Torrellas. There are also efforts in Formal Verification led by Gagandeep Singh, Professor at Illinois, Graph Applications by domain experts Karrie Karahalios, Professor at Illinois, Hanghang Tong, Professor at Illinois, and Tandy Warnow, Grainger Distinguished Chair in Engineering Professor at Illinois; and in Educational and Broadening Activities led by Colleen Lewis, Associate Professor at Illinois, and Tiffani Williams, Professor at Illinois
The researchers will work together, contributing their complementary expertise to common goals. In addition, there will be a yearly workshop where the PIs will invite faculty and students from disadvantaged communities and minority-focused institutions. The workshop will train faculty and students on scalable graph computing. Finally, there will be regular seminars that will be broadcasted widely.